/**
 * 插入排序
 */

/**
 * 
 * @param {*} A 已经排好序的数组
 * @param {*} x 要插入的元素
 */
function insert1(A = [], x) {
  // 遍历数组，从后往前 or 从前往后
  let p = A.length - 1  // 从后往前遍历

  while (p >= 0 && A[p] > x) { // 找到小于x的数据的位数，把x插入到该数据的后一位p+1
    p--
  }
  A.splice(p + 1, 0, x)
  return A
}


/**
 * 增加一个空位在末尾
 * 查找比x打的数据往后移动一位
 */
function insert2(A = [], x) {
  // 遍历数组，从后往前 or 从前往后
  let p = A.length - 1  // 从后往前遍历

  while (p >= 0 && A[p] > x) { // 找到小于x的数据的位数，把x插入到该数据的后一位p+1
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x
  return A
}
// let arr1 = insert1([1, 2, 3, 4, 6, 9], 8)
// let arr2 = insert2([1, 2, 3, 4, 6, 9], 8)
// console.log(arr1)
// console.log(arr2)


/**
 * 
 * @param {*} A 要排序的数组
 * @param {*} i 前i项数列是有序的
 * @param {*} x 要插入的数据
 * 采用增加一个空位思路
 * 找到指针
 */
function insert3(A, i, x) {

  let p = i - 1 // 前i项是排号的数据
  while (p >= 0 && A[p] > x) {
    A[p + 1] = A[p]
    p--
  }
  A[p + 1] = x

}

function insert_sort(nums = []) {// 使用插入排序排序数组nums

  for (let i = 0; i < nums.length; i++) {
    let x = nums[i]
    insert3(nums, i, nums[i]) // 表示前项是有序数列
  }
  return nums
}

let arr3 = insert_sort([1, 2, 8, 19, 3, 4, 6, 9])
console.log(arr3)